package linked.pratice;

import linked.Node;
import linked.DoubleLinkedListADT;

public class ReverseLinkedList {

    public static void main(String[] args) throws CloneNotSupportedException {
        DoubleLinkedListADT<Integer> link = new DoubleLinkedListADT<>();
        Node<Integer> node04 = new Node<>(4);
        Node<Integer> node01 = new Node<>(1);
        Node<Integer> node02 = new Node<>(2);
        Node<Integer> node03 = new Node<>(3);

        link.addLast(node01).addLast(node02).addLast(node03).addFirst(node04);

        reverse(link);

        link.showList();

    }


    public static void reverse(DoubleLinkedListADT list) throws CloneNotSupportedException {
        //获取头元素
        Node head = list.getHead();
        Node tail = list.getTail();
        Node temp;

        while (true){
            if (head==tail) break;


            //复制指针节点

            temp=head.clone();
            //清除指针的前后连接，避免addList时成为循环链表
            temp.next=null;
            temp.prev=null;
            head=head.next;

//            list.addLast(temp);
            if (tail.next==null){
                tail.next=temp;
                temp.prev=tail;
            }else {
                temp.next=tail.next;
                tail.next.prev=temp;
                tail.next=temp;
                temp.prev=tail;
            }

            list.removeFirst();


        }
    }
}
